Funkcja jednokierunkowa

Funkcja jednokierunkowa – funkcja, która jest łatwa do wyliczenia, ale trudna do odwrócenia. „Łatwa do wyliczenia” oznacza tu, że istnieje algorytm wielomianowy, który ją wylicza. „Trudna do odwrócenia” oznacza, że żaden wielomianowy algorytm probabilistyczny nie potrafi znaleźć elementu przeciwobrazu $f(x)$ z prawdopodobieństwem większym niż zaniedbywalne, jeśli $x$ jest wybrane losowo. Trudność dotyczy zatem średniego przypadku, a nie pesymistycznego, jak w większości problemów w teorii złożoności obliczeniowej (np. w problemach NP-trudnych).

Formalna definicja

Formalnie funkcje jednokierunkowe definiuje się na dwa sposoby:

Funkcja silnie jednokierunkowa to funkcja $f:\{0,1\}^{*}\to \{0,1\}^{*}$ taka, że:

• $f$ jest obliczalna w czasie wielomianowym
• Dla dowolnego $d\in \mathbb {N}$ i dowolnego wielomianowego algorytmu probabilistycznego $A,$ jeśli $k$ jest wystarczająco duże, to:

Pr$[A(f(x),1^{k})\in f^{-1}(f(x))|x\in _{R}\{0,1\}^{k}]\leqslant k^{-d}$

Innymi słowy, żaden algorytm probabilistyczny nie jest w stanie zgadnąć wartości argumentu z prawdopodobieństwem, które nie byłoby zaniedbywalnie małe.

Funkcja słabo jednokierunkowa to funkcja $f:\{0,1\}^{*}\to \{0,1\}^{*}$ taka że:

• $f$ jest obliczalna w czasie wielomianowym
• Istnieje $d\in \mathbb {N} ,$ takie że dla dowolnego wielomianowego algorytmu probabilistycznego $A,$ jeśli $k$ jest wystarczająco duże, to:

Pr$[A(f(x),1^{k})\notin f^{-1}(f(x))|x\in _{R}\{0,1\}^{k}]\geqslant k^{-d}$

Innymi słowy, każdy algorytm probabilistyczny, który ją odwraca, podaje błędną wartość z prawdopodobieństwem, które nie jest zaniedbywalnie małe.

Funkcje silnie jednokierunkowe są oczywiście również słabo jednokierunkowe. Choć istnienie tych drugich wydaje się znacznie bardziej prawdopodobne, można pokazać, że jeśli istnieją funkcje słabo jednokierunkowe, to istnieją również silnie jednokierunkowe.

Istnienie funkcji jednokierunkowych

Istnienie funkcji jednokierunkowych jest otwartym problemem w informatyce. Z faktu ich istnienia wynikałoby automatycznie, że P≠NP, co rozstrzygałoby najsłynniejszy problem w informatyce. Implikacja w drugą stronę nie jest znana – nie wiadomo, czy z P≠NP wynikałoby automatycznie istnienie funkcji jednokierunkowych. Wiąże się to z różnicą pomiędzy rozważaniem średniego i najgorszego przypadku w tych problemach.

Istnienie tych funkcji pozwoliłoby uzyskać wiele przydatnych w kryptografii narzędzi, między innymi:

• Generatory liczb pseudolosowych
• Protokoły zobowiązania bitowego
• Bezpieczne kody uwierzytelniające wiadomości
• Bezpieczne podpisy elektroniczne

Kandydaci na funkcje jednokierunkowe

Ponieważ do tej pory nie wiadomo, czy funkcje jednokierunkowe istnieją, w praktyce używa się kilku funkcji, które są o to podejrzewane: funkcji, dla których pomimo wysiłku wielu badaczy nie udało się znaleźć efektywnych algorytmów odwracających.

Mnożenie vs. faktoryzacja

Mnożenie liczb naturalnych jest łatwe algorytmicznie. Z drugiej strony jeśli pomnożymy przez siebie dwie duże liczby pierwsze (np. 34 961 i 49 369, wynik mnożenia to 1 725 989 609), znalezienie ich na podstawie iloczynu może być trudne. Mnożenie może być więc funkcją słabo jednokierunkową. Na tej funkcji opiera się w dużej mierze kryptosystem RSA.

Obecnie najlepszym znanym algorytmem faktoryzacji jest GNFS, którego złożoność wynosi $2^{O({(\log N)^{1/3}(\log \log N})^{2/3})}.$

Funkcja Rabina

Jeśli dla danego $N$ i $x<N$ wyliczymy $y=x^{2}$ (mod N), to można pokazać, że znalezienie $x$ na podstawie y jest algorytmicznie równie trudne jak faktoryzacja $N.$ Podnoszenie do kwadratu jest więc równie dobrym kandydatem na funkcję jednokierunkową jak mnożenie. Na tej funkcji oparty jest kryptosystem Rabina.

Potęgowanie vs. logarytm dyskretny

Jeśli dla danej liczby pierwszej $p$ oraz $g<p$ i $x<p$ wyliczymy $y=g^{x}$(mod p), to okazuje się, że nie znamy efektywnego algorytmu pozwalającego znaleźć właściwe $x$ na podstawie $g,$ $y$ i $p.$ Potęgowanie w ciele skończonym jest więc kandydatem na funkcję jednokierunkową. Opiera się na nim kryptosystem ElGamal.

Inne funkcje

Wszystkie trzy podane wyżej funkcje mogą być funkcjami jednokierunkowymi, ale wiadomo już, że można je łatwo odwracać, jeśli ma się do dyspozycji komputer kwantowy (używając Algorytmu Shora do faktoryzacji i kwantowej transformaty Fouriera do wyliczenia logarytmu dyskretnego). Istnieją inne funkcje podejrzewane o bycie funkcjami jednokierunkowymi, np. bazujące na różnych problemach NP-zupełnych. W praktyce ich bezpieczeństwo jest jednak znacznie słabiej zbadane.

Zobacz też

• funkcja skrótu

Bibliografia

• Oded Goldreich (2001). Foundations of Cryptography: Volume 1, Basic Tools. Cambridge University Press. ISBN 0-521-79172-3.
• Jonathan Katz and Yehuda Lindell (2007). Introduction to Modern Cryptography. CRC Press. ISBN 1-58488-551-3.